Integrated circuit memories are organized in a matrix of rows and columns, with a memory cell located at each intersection of a row and a column. When accessed during a read cycle, the memory decodes an address to enable one row line. The memory cells on the enabled row line provide their contents onto bit lines, or more commonly, on differential bit line pairs. When each memory cell provides its contents onto a bit line or a bit line pair, a sense amplifier detects a logic state of the signal and amplifies it. Then, further decoding may be performed. The speed at which the decoding takes place together with the sensing time determine the overall speed of the memory. The type of decoding depends on the type and use of the memory.
For example, many microprocessors now incorporate caches, which are on-chip high-speed memories. Caches increase the performance of the microprocessor by storing on-chip the contents of memory the microprocessor is most likely to access. A microprocessor with an on-chip instruction cache, for example, stores a portion of its program in the on-chip cache. If the instruction is in the cache, the microprocessor reads it from the high-speed cache rather than from slower, off-chip memory. Similarly, a microprocessor with a data cache stores a portion of the program's data on-chip. To determine whether a microprocessor memory access is from the cache, the cache compares the address the microprocessor places on the address bus with the address of data previously stored in the cache. This comparison of addresses is done with additional memory known as the tag cache array. The contents of the tag cache array are addresses whose data is located in the cache.
In cache circuits speed is critical. The speed of the comparison between the accessed address and the contents of the tag cache array must be minimized. Several techniques are used for determining whether the accessed address is one of the addresses located in the tag cache array. For example, in a fully-associative cache, all tag cache array entries are simultaneously compared with the input address. A two-way set-associative cache, however, first uses a portion of the input address to decode two possible tag cache array entries. The predecoded entries are then sensed and corresponding bit positions are compared to the remaining address bits of the input address. If the remaining address bits in the input address match one of the two decoded tag cache entries, then a "cache hit" has occurred, and the corresponding contents of the cache array are read onto the data bus. If none of the two entries match the input address, however, a "cache miss" has occurred and data from the memory address must be fetched from off-chip memory. Between the two-way set-associative and the fully associative caches is the four-way set associative cache, which decodes a portion of the incoming address to select four possible cache entries, and then performs the further comparison. Because there is a design trade-off between microprocessor performance and circuit area, set associative caches are often preferred. In order to optimize performance of the set associative cache, sensing time must be minimized.